#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/**
 * 原题: https://leetcode-cn.com/problems/possible-bipartition/
 * 视频讲解: https://www.bilibili.com/video/BV1ve411W76e?from=search&seid=16318031295990334767
 */

typedef enum Color {
  WHITE = -1,
  EMPTY = 0,
  BLACK = 1
} Color;

void free_mem(int N, int** graph, int* dislike_num, int* colors)
{
  for(int i = 0; i <= N; ++i)
    free(graph[i]);
  free(graph);
  free(dislike_num);
  free(colors);
}

bool dfs(int** graph, int cur_index, Color cur_color, int* colors, int* dislike_num)
{
  int i;

  // 如果 cur 当前节点，已经被 染色过，则判断 当前要染的色，是否等于，已经被染成的颜色
  if (EMPTY != colors[cur_index])
    return cur_color == colors[cur_index]; // true: 染色成功，ralse: 染色失败

  // 先对 cur 当前节点，进行 染色
  colors[cur_index] = cur_color;

  // 遍历 graph[cur] 所有 不喜欢的 顶点，使用【取反】的颜色，进行染色
  for (i = 0; i < dislike_num[cur_index]; ++i)
  {
    // 对 graph[cur] 【取反】染色
    if (!dfs(graph, graph[cur_index][i], -cur_color, colors, dislike_num))
    {
      colors[cur_index] = EMPTY;
      return false; // 只要有【一个】顶点【染色失败】，说明这一次的 1..N 序列【染色失败】
    }
  }

  // 全部染色成功
  return true;
}

bool possibleBipartition(int N, int** dislikes, int dislikesSize, int* dislikesColSize)
{
	int i;

  // 1、定义一个 (N+1)x(N+1) 大小的 邻接矩阵
  // graph[i][j] 的含义:
  // - gorup[1][1] = 2 : 元素 1, 第 1 个 不喜欢 元素 2, 此时 dislike_num[1] = 1
  // - gorup[1][2] = 3 : 元素 1, 第 2 个 不喜欢 元素 3, 此时 dislike_num[1] = 2
  // - gorup[2][3] = 4 : 元素 2, 第 3 个 不喜欢 元素 4, 此时 dislike_num[2] = 3
	int** graph = (int**)malloc(sizeof(int*) * (N + 1));
	for (i = 0; i <= N; ++i)
  {
		graph[i] = (int*)malloc(sizeof(int) * (N + 1));
		memset(graph[i], 0, sizeof(int) * (N + 1));
	}

  // 2、定义一个 N+1 长度的数组, 记录 元素 i 不喜欢（dislike） 的顶点【总个数】
	int* dislike_num = (int *)malloc(sizeof(int) * (N + 1));
	memset(dislike_num, 0, sizeof(int) * (N + 1));

  // 3、定义一个 N+1 长度的数组, 记录 元素 i 的【颜色】
  int *colors = (int *)malloc(sizeof(int) * (N + 1));
  memset(colors, EMPTY, sizeof(int) * (N + 1));

  // 4、按照给定的 dislikes = [[1,2],[1,3],[2,4]] 设置到 邻接矩阵
	for (i = 0; i < dislikesSize; ++i)
  {
		graph[ dislikes[i][0] ][ dislike_num[ dislikes[i][0] ] ] = dislikes[i][1];
    printf("graph[%d][%d] = %d\n", dislikes[i][0], dislike_num[ dislikes[i][0] ], dislikes[i][1]);

    dislike_num[ dislikes[i][0] ]++;
    printf("dislike_num[%d]++\n", dislikes[i][0]);

		graph[ dislikes[i][1] ][ dislike_num[ dislikes[i][1] ] ] = dislikes[i][0];
		printf("graph[%d][%d] = %d\n", dislikes[i][1], dislike_num[ dislikes[i][1] ], dislikes[i][0]);

		dislike_num[ dislikes[i][1] ]++;
    printf("dislike_num[%d]++\n", dislikes[i][1]);
	}
  // 如上 for 执行语句:
  // graph[1][0] = 2
  // dislike_num[1]++
  // graph[2][0] = 1
  // dislike_num[2]++
  // graph[1][1] = 3
  // dislike_num[1]++
  // graph[3][0] = 1
  // dislike_num[3]++
  // graph[2][1] = 4
  // dislike_num[2]++
  // graph[4][0] = 2
  // dislike_num[4]++

  // 5、对 1..N 序列遍历，分别按照【白色】和【黑色】染色
  for (i = 0; i <= N; ++i)
  {
    // 如果节点【已经被染色】，则不再对这个顶点进行染色
    if (EMPTY != colors[i])
      continue;

    // 先按照【白色】进行染色顶点，如果染色【成功】则对【下一个】顶点染色
    if (dfs(graph, i, WHITE, colors, dislike_num))
      continue;

    // 如果上面先按照【白色】染色【失败】，那么再尝试按照【黑色】染色，
    // 如果还是 染色【失败】，那么此次 1..N 序列，就是染色【失败】
    if (!dfs(graph, i, -WHITE, colors, dislike_num))
    {
      free_mem(N, graph, dislike_num, colors);
      return false;
    }
  }

  // 6、全部顶点染色成功
  free_mem(N, graph, dislike_num, colors);
	return true;
}

int main(int argc, const char * argv[])
{
  {
    int  dislike_0[2] = {1, 2};
    int  dislike_1[2] = {1, 3};
    int  dislike_2[2] = {2, 4};
		int* dislikes[3]  = {dislike_0, dislike_1, dislike_2};
    int  dislikesColSize = 0;
		bool ret = possibleBipartition(4, dislikes, 3, &dislikesColSize);
		printf("ret: %d, dislikesColSize: %d\n", ret, dislikesColSize);
  }

  {
    int  dislike_0[2] = {1, 2};
    int  dislike_1[2] = {1, 3};
    int  dislike_2[2] = {2, 3};
    int* dislikes[3]  = {dislike_0, dislike_1, dislike_2};
    int  dislikesColSize = 0;
    bool ret = possibleBipartition(4, dislikes, 3, &dislikesColSize);
    printf("ret: %d, dislikesColSize: %d\n", ret, dislikesColSize);
  }

  {
    int  dislike_0[2] = {1, 2};
    int  dislike_1[2] = {2, 3};
    int  dislike_2[2] = {3, 4};
    int  dislike_3[2] = {4, 5};
    int  dislike_4[2] = {5, 1};
    int* dislikes[5]  = {dislike_0, dislike_1, dislike_2, dislike_3, dislike_4};
    int  dislikesColSize = 0;
    bool ret = possibleBipartition(5, dislikes, 5, &dislikesColSize);
    printf("ret: %d, dislikesColSize: %d\n", ret, dislikesColSize);
  }

  return 0;
}
